package madixin.t236;

import java.util.*;

class Solution {

    /**
     * 使用父指针迭代
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return root;
        }
        Map<TreeNode, TreeNode> index = new HashMap<>();
        Stack<TreeNode> stack = new Stack<>();
        index.put(root, null);
        stack.push(root);
        while (!index.containsKey(p) || !index.containsKey(q)) {
            TreeNode curNode = stack.pop();
            if (curNode.left != null) {
                index.put(curNode.left, curNode);
                stack.push(curNode.left);
            }
            if (curNode.right != null) {
                index.put(curNode.right, curNode);
                stack.push(curNode.right);
            }
        }

        List<TreeNode> pAncestor = new LinkedList<>();
        while (p != null) {
            pAncestor.add(p);
            p = index.get(p);
        }

        while (!pAncestor.contains(q)) {
            q = index.get(q);
        }
        return q;
    }


    /**
     * 递归
     */
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor1(root.left, p, q);
        TreeNode right = lowestCommonAncestor1(root.right, p, q);

        if (left != null && right != null) {
            return root;
        } else if (left != null) {
            return left;
        }
        return right;
    }
}